package com.mj.listen1._07AVL树.tree;


import com.mj.listen1._07AVL树.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    // 根节点
    protected Node<E> root;

    // 元素的数量
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空所有元素
    public void clear() {
        root = null;
        size = 0;
    }

    /**********      遍历      **********/
    // 前序遍历
    public void preorderTraversal() {
        this.preorderTraversal(root);
    }

    private void preorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }

        // 先访问父节点
        System.out.println(node.element);
        // 再访问左边
        preorderTraversal(node.left);
        // 最后右边
        preorderTraversal(node.right);
    }

    // 中序遍历
    public void inorderTraversal() {
        this.inorderTraversal(root);
    }

    private void inorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }

        // 先访问左边
        inorderTraversal(node.left);
        // 再中间访问父节点
        System.out.println(node.element);
        // 最后访问右边
        inorderTraversal(node.right);
    }

    // 后序遍历
    public void postorderTraversal() {
        this.postorderTraversal(root);
    }

    private void postorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }

        // 先访问左边
        postorderTraversal(node.left);
        // 再中间访问右边
        postorderTraversal(node.right);
        // 最后访问父节点
        System.out.println(node.element);
    }

    // 层序遍历
    public void levelOrderTranversal() {
        if (root == null) {
            return;
        }
        Node<E> node = root;
        Queue<Node<E>> queue = new LinkedList<>();
        // 往队列填充根节点
        queue.offer(node);

        while (!queue.isEmpty()) {
            // 取出根节点输出
            node = queue.poll();
            System.out.println(node.element);

            // 添加左孩子到队列中
            if (node.left != null) {
                queue.offer(node.left);
            }

            // 添加右孩子到队列中
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**********      遍历      **********/

    // 获取二叉搜索树的高度，其实就是根节点的高度
    public int height2() {
        // 通过递归的方式
        return height(root);
    }

    // 获取node节点的高度
    private int height(Node<E> node) {
        if (node == null) return 0;
        // 递归。节点的高度 = 1 + 左右孩子节点的高度的最大值
        return 1 + Math.max(height(node.left), height(node.right));
    }

    // 获取二叉搜索树的高度。非递归，遍历的方式。
    // 借用层序遍历
    public int height() {
        if (root == null) {
            return 0;
        }
        // 记录高度
        int height = 0;
        // 记录每一层的个数，默认就是1个
        int levelSize = 1;
        Node<E> node = root;
        Queue<Node<E>> queue = new LinkedList<>();
        // 往队列填充根节点
        queue.offer(node);

        while (!queue.isEmpty()) {
            // 取出根节点输出
            node = queue.poll();
            levelSize--;

            // 添加左孩子到队列中
            if (node.left != null) {
                queue.offer(node.left);
            }

            // 添加右孩子到队列中
            if (node.right != null) {
                queue.offer(node.right);
            }

            if (levelSize == 0) {
                // 说明换行了，记录下一行的数量，下一行的数量。恰好是队列的大小
                levelSize = queue.size();
                height++;// 换行了
            }
        }
        return height;
    }

    // 判断二叉树是否是完全二叉树
    public boolean isCompleteTree2() {
        if (root == null) {
            return false;
        }
        // 后续的节点必须是叶子节点
        boolean mastIsLeaf = false;
        Node<E> node = root;
        Queue<Node<E>> queue = new LinkedList<>();
        // 往队列填充根节点
        queue.offer(node);

        while (!queue.isEmpty()) {
            node = queue.poll();

            // 必须是叶子节点，但是当前遍历到的节点不是叶子节点，那么久不是完全二叉树
            if (mastIsLeaf && !node.isLeaf()) {
                return false;
            }

            if (node.hasTwoChildren()) {
                // 孩子节点入队
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right != null) {
                // 没有左孩子，有右孩子
                return false;
            } else {
                // 此时后续的节点必须都是叶子节点
                mastIsLeaf = true;
                // 后面遍历的节点全部为叶子节点，才是完全二叉树
                if (node.left != null) {// 7 4 9 2 1不加这行代码会报错
                    queue.offer(node.left);
                }
            }
        }
        return true;
    }

    // 判断二叉树是否是完全二叉树 最终版
    public boolean isCompleteTree() {
        if (root == null) {
            return false;
        }
        // 后续的节点必须是叶子节点
        boolean mastIsLeaf = false;
        Node<E> node = root;
        Queue<Node<E>> queue = new LinkedList<>();
        // 往队列填充根节点
        queue.offer(node);

        while (!queue.isEmpty()) {
            node = queue.poll();

            if (mastIsLeaf && !node.isLeaf()) {
                return false;
            }

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {// node.left == null
                return false;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else {// node.right == null
                // node.left == null || node.left != null
                mastIsLeaf = true;
            }
        }
        return true;
    }

    /**
     * 根据传入的节点, 返回该节点的前驱节点 (中序遍历)
     *
     * @param node
     * @return
     */
    protected Node<E> predecessor(Node<E> node) {
        Node<E> p = node.left;
        // 左子树不为空
        if (p != null) {
            // left.right
            while (p.right != null) {
                p = p.right;
            }
            // 左子树的底部最右侧的节点
            return p;
        }

        // 左子树为空
        // 去找parent，parent不为空，node在parent的左子树中，继续往上找parent
        if (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        // left == null && node.parent == null。返回null
        return node.parent;
    }

    /**
     * 根据传入的节点, 返回该节点的后驱节点 (中序遍历)
     *
     * @param node
     * @return
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) return node;

        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }

        // node.right为空
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>) node;
        String parentStr = "null";
        if (myNode.parent != null) {
            parentStr = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentStr + ")";
    }

    protected static class Node<E> {
        public Node<E> left;
        public Node<E> right;
        public Node<E> parent;
        public E element;

        /**
         * 是否是叶子
         *
         * @return
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 当前节点是否有两个孩子
         */
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        // 这里不初始化左,右结点,因为不常用,比如所叶子结点,就没有左右结点
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        /**
         * 判断自己是否是左孩子
         *
         * @return
         */
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        /**
         * 判断自己是否是右孩子
         *
         * @return
         */
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }
    }
}
